package com.practice.sequence;

import java.util.ArrayList;

/**
 * Given an array of integer a[], each represents height of one side of a 
 * bucket. The length of bucket is the difference of number index. Calculate 
 * the maximum capacity of bucket using two numbers of this array.
 */
public class MaxCapacity {
	public int getMax(int[] a) {
		if (a.length < 2) return 0;
		
		ArrayList<Integer> l = new ArrayList<Integer>();
		ArrayList<Integer> r = new ArrayList<Integer>();
		
		// scan from left to right, generate an increasing sequence
		l.add(0);
		int max = a[0];
		for (int i=1; i<a.length; i++) {
			if (a[i] > max) {
				l.add(i);
				max = a[i];
			}
		}
		
		// scan from right to left, generate another increasing sequence
		r.add(a.length - 1);
		max = a[a.length - 1];
		for (int i=a.length-2; i>=0; i--) {
			if (a[i] > max) {
				r.add(i);
				max = a[i];
			}
		}
		
		// using numbers from two sequences to form bucket, calculate max 
		// capacity.
		int left = 0;
		int right = 0;
		max = 0;
		
		do {
			int i = l.get(left);
			int j = r.get(right);
			int h;
			if (a[i] >= a[j]) {
				h = a[j];
				right++;
			}
			else {
				h = a[i];
				left++;
			}
			
			if (h*(j-i) > max) max = h*(j-i);
		} while (left<l.size() && right<r.size());
		
		return max;
	}
}
